問：n個の要素からなる集合の部分集合は全部で2^n個あることを示せ
from 部分集合
問：n個の要素からなる集合の部分集合は全部で2^{n}個あることを示せ
は～…また問題が生えてきたよ…
勝手に問題が生えてくる先進的な数学テキスト
1. 1個の要素からなる集合の部分集合は？
仮にA=\{1\}の場合
部分集合は\{1\}, \{\}……一個？2個か
他にも部分集合があるんかな
下記のLinksの中にヒントが
閉集合……？
空集合はある集合の部分集合になるか？の答えはYesなので...？
部分集合は\{1\}, \{\}……2個か
2. 2個の要素からなる集合の部分集合は？
A=\{1, 2\}
部分集合は以下の４つ
\{\}空集合
\{1\}1のみ
\{2\}2のみ
\{1,2\}1と2
これも部分集合に入るのか？
>部分集合の定義から，A⊂Aは明らかに成り立ちます.一方，A⊂BかつB⊂Aであれば，A=Bが成り立ちます. したがって，A⊂BかつB⊂Aが成り立つことと，A=Bであることは同値です.(p.3)
入るのか…
これ確率で見たやつだな
n個の互いに異なるボールから任意個のボールをとってくるときの総数
3. 3個の要素からなる集合の場合は？
A=\{1,2,3\}
部分集合は…8つ
\{\}空集合
要素が1個のみ：3つ
\{1\}\{2\}\{3\}
要素が2個：3つ
\{1,2\}\{2,3\}\{1,3\}
要素が3個：1つ
\{1,2,3\}
たしかに2^nの形式になっとるな
ここまでのあらすじ
練習問題
| 部分集合の数 | ||
| 1 | 2 | 2^1 |
| 2 | 4 | 2^2 |
| 3 | 8 | 2^3 |
| ... | ||
| n | 2^n(?) |
案1：1のとき2、2のとき4、3のとき8になります。これはよく見ると2^nの形になってます。だからそうなります！！！！
だめそう
すべての事例についていちいち例示しないといけなくなる
案2：\sout{nCr}_{n}\mathrm{C}_{r}を使おう
やや入力が面倒なのですが{}_{n}C_{r}または{}_{n}\mathrm{C}_{r}とした方が誤解の恐れが少ないと思います
nCr=n \times C \times rにみえる
\binom{n}{r}や小さめに表示される\tbinom{n}{r}という書き方もあります
なるほど、下付きで表現するんですね
直そう。中に線引くのはどうやってやるんだったかな
\sout{abc}
[$ \sout{abc}] _{n}\mathrm{C}_{r}
[$ _{n}C_{r}] おおー書けた
……といいつつこれなんだったか忘れたんだよなあ
数学ガールの秘密ノートをよんでみよ
場合の数の話を買ってなかったことが判明。なんともはや
ライブ講義 大学1年生のための数学入門を引っ張り出した
第3章 代数にこの書き方の秘密がのっているぞ
>さて，異なるn個のものからm個を選び出す場合(選び出すだけで，並べたりはしない)の数を，_{n}\mathrm{C}_{m} と書こう。_{n}\mathrm{C}_{m} はどんな式になるだろうか?(p.30)
前段階で_{n}\mathrm{P}_{m}、順列の計算をしている
_{n}\mathrm{P}_{m}と_{n}\mathrm{C}_{m}の差異は何か？
_{n}\mathrm{P}_{m}は「異なるn個からm個選んで並べる」場合の数
順列(permutation)と呼ぶ
_{n}\mathrm{P}_{m}=n\times(n-1)\times\cdots\times(n-m+1)
これが3個の内から3個並べる場合だとどうなるか？
_{3}\mathrm{P}_{3}=3\times2\times1=6
すなわち3!になるのか
( 0M0)<3!
_{n}\mathrm{C}_{m}は「異なるn個からm個選ぶ」場合の数
プログラマの数学(p.134)を見る
abcdの4つの文字から3つの文字を抜き出す。このときパターンはいくつあるか？
1. abc
2. abd
3. acb
4. acd
5. adb
6. adc
7. bac
8. bad
9. bca
10. bcd
11. bda
12. bdc
13. cab
14. cad
15. cba
16. cbd
17. cda
18. cdb
19. dab
20. dac
21. dba
22. dbc
23. dca
24. dcb
24通りだな！(ブルートフォース)
この24通りのうち組み合わせが同じものがある
組み合わせ
| 1 | abc | acb | bac | bca | cab | cba |
| 2 | abd | adb | bad | bda | dab | dba |
| 3 | acd | adc | cad | cda | dac | dca |
| 4 | bcd | bdc | cbd | cdb | dbc | dcb |
したがって「abcdの4つの文字から3つの文字を抜き出す組み合わせ」は4通りだといえる
>5枚から3枚を選ぶ組み合わせの総数は、次のように考えるとよいでしょう。
> ・まず、順列と同様に「順序を考えて」数える。
> ・重複して数えてしまった分(重複度)で割り算する。
プログラマの数学p.134
今回の場合は
1. 「順列と同様に「順序を考えて」数える」と、24通り
_{4}\mathrm{P}_{3}=4\times3\times2=24
2. 「重複して数えてしまった分(重複度)で割り算する」
重複した分は3つの文字の置換の総数
3つの文字の並べ方は_{3}\mathrm{P}_{3}=3\times2\times1=6
したがって
\frac{_{4}\mathrm{P}_{3}}{_{3}\mathrm{P}_{3}}=\frac{24}{6}=4
したがって組み合わせの計算は
_{n}\mathrm{C}_{m}=\frac{_{n}\mathrm{P}_{m}}{_{m}\mathrm{P}_{m}}
さーて戻ってきた。
では、集合の部分集合の数をどう表すかの問題だ
パターンは二項係数に似てるんだよな
1,1
1,2,1
1,3,3,1
この数をうまく足す方法があれば良い
nとn+1を…こう…上手く使って…
n個の要素から、0〜n個選ぶ組み合わせの総数はどうなるか？
0個選ぶってなんだ…？
1. n個から0個選ぶ場合
_n\mathrm{C}_{0}？
こんなことできるんか？
_{n}\mathrm{P}_{m}=n\times(n-1)\times\cdots\times(n-m+1)
なのでm=0なら
\sout{_{n}\mathrm{P}_{0}=n\times(n-0+1)=n(n+1)}
ここに誤りがあります。色々と方法はありますが、次のように考えてみましょう
{}_{n}\mathrm{P}_{m}=n\times(n-1)\times\cdots\times(n-m+1)=\frac{n!}{(n-m)!}
（コメント：階乗は分かります？）
したがって{}_{n}\mathrm{P}_{0}=\frac{n!}{n!}=1
ついでながら書いておくと、0!=1に注意して{}_{n}\mathrm{C}_{m}=\frac{{}_{n}\mathrm{P}_{m}}{{}_{m}\mathrm{P}_{m}}=\frac{n!}{m!(n-m)!}となります
あざます！
帰ったらなぜズレたのか考えます！
階乗は1*2*3を3!で表すという乃木わかる程度にわかる
誰？
_{m}\mathrm{P}_{m}=m\times(m-m+1)=m
なのでm=0なら0通り…？
ゼロ除算というのになりそう。このルートはダメだ
_{n}\mathrm{C}_{0}=\frac{_{n}\mathrm{P}_{0}}{_{0}\mathrm{P}_{0}}=\frac{n(n+1)}{0}=?
計算をミスしてはいないか？
何も選ばない場合(「ば」、「い」がややこしい)
要素は1つもないので空集合になる
2. n個から1個えらぶ
sum関数みたいなことをやりたいのだがうーむ
これはあれだ、\Sigmaだ
総和←赤リンク
総和ってどうやったっけな……
数列の和を表すのには\sumを使う
>数列(a_1, a_2, a_3,\cdots)について，第p項から第q項までの和a_p+a_{p+1}\cdots+a_qのことを(ただしp, qは整数で，p\leq qとする)，
> \sum_{n=p}^qa_n
>と書く。(定義)
総和ルートだと数列に落とし込まないといけない
n-1個とn個だとどう表現するのか
>いまここ
恐らく"サブクエスト"に時間がかかりすぎるのは不本意だと思うので、なるべくさんのやろうとしている方法に従いつつ解答(の一歩手前)を考えてみました
（注意：これが唯一の証明方法あるいは最も簡単な証明方法というわけではありません。たぶん）
\mathfrak{P}(A)は集合の集合です
\mathfrak{P}はPower setの頭文字Pのフラクトゥール
\#Aや\mathrm{card}(A)とも表す
いまX_{3}=\{1,2,3\}とおき、|\mathfrak{P}(X_{3})|=2^{3}となることを示します
/villagepump/問：n個の要素からなる集合の部分集合は全部で2^n個あることを示せ#638f53415e90c00000a5ac3cの例に従って集合A \in \mathfrak{P}(X_{3})を要素の個数で分類します（いま|X_{3}|=3より、0 \le |A| \le 3であることに注意）
|A|=0の場合：A = \emptyset
3つの相異なるものから何も選ばない方法は{}_{3}\mathrm{C}_{0}通り
よって|\{A\in\mathfrak{P}(X_{3}) ; |A|=0\}|={}_{3}\mathrm{C}_{0}
|A|=1の場合：A \in \{\{1\},\{2\},\{3\}\}
3つの相異なるものから1つのものを選ぶ方法は{}_{3}\mathrm{C}_{1}通り
よって|\{A\in\mathfrak{P}(X_{3}) ; |A|=1\}|={}_{3}\mathrm{C}_{1}
|A|=2の場合：A \in \{\{1,2\},\{2,3\},\{1,3\}\}
3つの相異なるものから2つのものを選ぶ方法は{}_{3}\mathrm{C}_{2}通り
よって|\{A\in\mathfrak{P}(X_{3}) ; |A|=2\}|={}_{3}\mathrm{C}_{2}
|A|=3の場合：A =\{1,2,3\}
3つの相異なるものから3つのものを選ぶ方法は{}_{3}\mathrm{C}_{3}通り
よって|\{A\in\mathfrak{P}(X_{3}) ; |A|=3\}|={}_{3}\mathrm{C}_{3}
したがって（一般のnに対して書く際は分解を具体的に書かなくても良いですが、今は例を扱っているため丁寧に書くと）
\begin{aligned}\mathfrak{P}(X_{3})&=\{\emptyset\}\sqcup \{\{1\},\{2\},\{3\}\} \sqcup \{\{1,2\},\{2,3\},\{1,3\}\} \sqcup \{\{1,2,3\}\} \\ &=\bigsqcup_{m=0}^{3}\{A\in\mathfrak{P}(X_{3}) ; |A|=m\}\end{aligned}
となり（|A\sqcup B|=|A|+|B|に注意して）
|\mathfrak{P}(X_{3})|=\sum_{m=0}^{3}|\{A\in\mathfrak{P}(X_{3}) ; |A|=m\}|=\sum_{m=0}^{3}{}_{3}\mathrm{C}_{m}
以上の例における3をnに変えて全体を良い感じに書き直すと、一般の場合の証明になります
ありがとうございます
これは…………どうしたものかな
思ってたよりも相当レベルの高い地帯に迷い込んでたのに気づいたときの気持ち
これ単体で読解しないとどうにもならん
見た目/言葉遣いが仰々しいのでぎょっとされたかもしれませんね...
とはいえ、日常的な言葉というか口語で説明されていたことを数学語(?)に書き直しただけなので、噛み砕けばそんなに高尚なことはしていないはず
ネタバレが生えてきた！
解けるまで見ないぞ
まあ和の計算はメインテーマではない気もしますが…
sore ha soudesu...
n=1
| はいる | はいらない | |
| 1 | {} | |
| 1 | {1} |
n=2
| はいる | はいらない | |
| 1,2 | {} | |
| 1 | 2 | {1} |
| 2 | 1 | {2} |
| 1,2 | {1,2} |
要素が一つ増えるたびに組み合わせが×2通りになる、なので2^nになる？
言葉が足りない感じ